/**
 * FileName: Exercise1805.c
 * ----------------------------------------------------------------------------------------------------
 * 18.5 Show, in the style of Figure 18.6, the progress of the search if the search function is modified to
 * scan the vertices in reverse order (from $V-1$ down to $0$).
 *
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

//边相关
typedef struct {
    int v;
    int w;
}
Edge;

//图相关
typedef struct graph *Graph;
struct graph {
    int V;
    int E;
    int** adj;
};

#define dfsR2 search

static int cnt;
static int* pre; // 可修改为动态分配

int depth = 0; // 全局变量表示递归深度，用来控制缩进量

//辅助函数声明
void HELPinit(int);
void HELPcleanUp();
int** MATRIXinit(int, int, int);
Edge EDGE(int, int);
void GRAPHshow(Graph);
void dfsR(Graph, Edge);
void printIndent();
void printPre(int);
void dfsR2(Graph, Edge);
void show(char*, Edge);

//图操作声明
Graph GRAPHinit(int);
void GRAPHinsertE(Graph, Edge);
void GRAPHremoveE(Graph, Edge);
int GRAPHedges(Edge [], Graph);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);

//辅助函数实现
void HELPinit(int maxV) {
    //全局变量初始化
    cnt = 0;
    int v;
    pre = malloc(maxV * sizeof(int));
    for (v = 0; v < maxV; v++) {
        pre[v] = -1;
    }
    depth = 0;
}

void HELPcleanUp() {
    free(pre);
}
/**
 * Program 17.4 Adjacency-matrix allocation and initialization
 * -------------------------------------------------------------------------------------------------------------
 * This program uses the standard C array-of-arrays representation for the two-dimensional adjacency matrix (see Section 3.7).
 * It allocates `r` rows with `c` integers each, then initializes all entries to the value `val`.
 *
 * The call `MATRIXinit(V, V, 0)` in Program 17.3 takes time proportional to $V^2$ to create a matrix that
 * represents a V-vertex graph with no edges.
 *
 * For small $V$, the cost of $V$ calls to `malloc` might predominate.
 */
int** MATRIXinit(int r, int c, int val) {
    int i;
    int j;
    int** t = malloc(r * sizeof(int*));
    for (i = 0; i < r; i++) {
        t[i] = malloc(c * sizeof(int));
    }
    for (i = 0; i < r; i++) {
        for (j = 0; j < c; j++) {
            t[i][j] = val;
        }
    }
    return t;
}

Edge EDGE(int v, int w) {
    Edge edge;
    edge.v = v;
    edge.w = w;
    return edge;
}

void GRAPHshow(Graph G) {
    int i;
    int j;
    printf("%d vertices, %d edges\n", G->V, G->E);

    //邻接列表
    for (i = 0; i < G->V; i++) {
        printf("%2d:", i);
        for (j = 0; j < G->V; j++) {
            if (G->adj[i][j] == 1) {
                printf(" %2d", j);
            }
        }
        printf("\n");
    }
    // //邻接矩阵
    // for (i = 0; i < G->V; i++) {
    //     printf("%2d:", i);
    //     for (j = 0; j < G->V; j++) {
    //         printf(" %2d", G->adj[i][j]);
    //     }
    //     printf("\n");
    // }
}

/**
 * Program 18.1 Depth-first search (adjacency-matrix)
 * --------------------------------------------------------------------------------------------------------------------
 * This code is intended for use with a generic graph-search ADT function that
 * - initializes a counter `cnt` to 0 and all of the entries in the vertex-indexed array `pre` to -1,
 * - then calls search once for each connected component (see Program 18.3),
 * assuming that the call `search(G, EDGE(v, v))` marks all vertices in the same connected component as `v`
 * (by setting their `pre` entries to be nonnegative).
 *
 * Here, we implement `search` with a recursive function `dfsR` that visits all the vertices connected to `e.w`
 * by scanning through its row in the adjacency matrix and
 * calling itself for each edge that leads to an unmarked vertex.
 * --------------------------------------------------------------------------------------------------------------------
 * 递归版dfs
 * @param G
 * @param edge
 */
void dfsR(Graph G, Edge e) {
    int t;
    int w = e.w;
    Edge x;
    pre[w] = cnt++;
    for (t = 0; t < G->V; t++) {
        if (G->adj[w][t] != 0) {
            x = EDGE(w, t);
            if (pre[t] == -1) {
                dfsR(G, x);
            }else if (t == e.v) {
                // parent link
            }else if (pre[t] < pre[w]) {
                // back link
            }else if (pre[t] > pre[w]) {
                // down link
            }
        }
    }

}

void printIndent() {
    int i;
    for (i = 0; i < depth; i++) {
        printf("  "); // 每层缩进2个空格
    }
}

void show(char* key, Edge e) {
    printIndent();
    printf("%d-%d %s\n", e.v, e.w, key);
}

void dfsR2(Graph G, Edge e) {
    int t;
    int w = e.w;
    Edge x;

    show("tree", e);
    depth++;
    pre[w] = cnt++;

    for (t = G->V-1; t >= 0; t--) {
        if (G->adj[w][t] != 0) {
            x = EDGE(w, t);
            if (pre[t] == -1) {
                // tree link
                dfsR2(G, x);
            }
            else if (t == e.v) {
                // parent link
                show("", x);
            }else if (pre[t] < pre[w]) {
                // back link
                show("", x);
            }else if (pre[t] > pre[w]) {
                // down link
                show("", x);
            }
        }
    }
    depth--;
}

void printPre(int maxV) {
    int i;
    for (i = 0; i < maxV; i++) {
        if (pre[i] == -1) {
            printf("* ");
        }else {
            printf("%d ", pre[i]);
        }
    }
    printf("\n");
}

//图操作函数实现
Graph GRAPHinit(int V) {
    Graph G = malloc(sizeof(*G));
    G->V = V;
    G->E = 0;
    G->adj = MATRIXinit(V, V, 0);
    return G;
}

void GRAPHinsertE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    if (G->adj[v][w] == 0) {
        G->E++;
    }
    G->adj[v][w] = 1;
    G->adj[w][v] = 1;
}

void GRAPHremoveE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    if (G->adj[v][w] == 1) {
        G->E--;
    }
    G->adj[v][w] = 0;
    G->adj[w][v] = 0;
}
int GRAPHedges(Edge a[], Graph G) {
    int v;
    int w;
    int E = 0;
    for (v = 0; v < G->V; v++) {
        for (w = v+1; w < G->V; w++) {
            if (G->adj[v][w] == 1) {
                a[E++] = EDGE(v, w);
            }
        }
    }
    return E;
}

Graph GRAPHcopy(Graph G) {
    Graph copy = GRAPHinit(G->V);
    int i;
    int j;
    for (i = 0; i < G->V; i++) {
        for (j = 0; j < G->V; j++) {
            if (G->adj[i][j] != 0) {
                GRAPHinsertE(copy, EDGE(i, j));
            }
        }
    }
    return copy;

}

void GRAPHdestroy(Graph G) {
    int i;
    for (i = 0; i < G->V; i++) {
        free(G->adj[i]);
    }
    free(G->adj);
    free(G);
}

//测试函数声明
void test_dfs();

int main(int argc, char *argv[]) {
    test_dfs();
    return 0;
}

//测试函数实现
void test_dfs() {
    int V = 8;
    Graph G = GRAPHinit(V);
    HELPinit(G->V);

    GRAPHinsertE(G, EDGE(0, 2));
    GRAPHinsertE(G, EDGE(0, 5));
    GRAPHinsertE(G, EDGE(0, 7));
    GRAPHinsertE(G, EDGE(1, 7));
    GRAPHinsertE(G, EDGE(2, 6));
    GRAPHinsertE(G, EDGE(3, 4));
    GRAPHinsertE(G, EDGE(3, 5));
    GRAPHinsertE(G, EDGE(4, 5));
    GRAPHinsertE(G, EDGE(4, 6));
    GRAPHinsertE(G, EDGE(4, 7));

    // GRAPHshow(G);
    dfsR2(G, EDGE(0, 0));

    GRAPHdestroy(G);
    HELPcleanUp();
}
